namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0063. 不同路径 II")]
    public class No0063_UniquePathsWithObstacles : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(UniquePathsWithObstacles,
                new int[][] {
                    new int[] {0,0,0},
                    new int[] {0,1,0},
                    new int[] {0,0,0}
                }, 2);
        }

        public int UniquePathsWithObstacles(int[][] obstacleGrid)
        {
            int n = obstacleGrid.Length, m = obstacleGrid[0].Length;
            int[] f = new int[m];
            f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (obstacleGrid[i][j] == 1)
                    {
                        f[j] = 0;
                        continue;
                    }
                    if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0)
                    {
                        f[j] += f[j - 1];
                    }
                }
            }
            return f[m - 1];
        }
    }
}
